1. Technical Field
This invention relates to information processors, and more particularly, to an information processor having a number of interconnected processing cells with randomly triggered adaptive cell thresholds.
2. Discussion
Of the many problems that information processors are used to solve, optimization problems of the general class of constrained assignment problems are among the most difficult. This is because constrained assignment problems often are not solvable with a single solution but there may be a range of solutions of which the "best" solution is sought. In general, assignment problems involve choosing a particular solution where there are more choices than there are possible solutions. Often one entity is to be selected from among many and assigned to one and only one other entity in such a way to force the entire assignment over all entities to be optimal in some sense. Where individual "costs" are assigned to each entity-to-entity mapping the problem becomes one of minimizing the total cost. Examples of assignment problems include optimal plot-to-track correlation processing, the traveling salesman problem, optimal weapons allocation, deghosting for angle-only (passive) targets detected by three or more sensors, computerized tomography, multi-beam acoustic and ultrasound tracking, nuclear particle tracking, etc.
Previous approaches to assignment problems have emphasized solutions in software on general purpose computers. One disadvantage with software solutions to assignment problems is that they require massive computational power and are exceedingly slow for application to real-time or near-real-time problems such as angle-only target location problems. This is because, these problems frequently involve a "combinatorial explosion", an exponential blowup in the number of possible answers. Thus, to solve the deghosting problem, conventional solutions, even using advanced state of the art array and parallel processors, have difficulty handling real-time problems of realistic sizes. For example, conventional solutions of the deghosting problem are sufficiently fast up to about 15 targets, but become exponentially computation-bound beyond that. For numbers of targets in the range of 30 or so, typical software approaches using integer programming techniques could require virtually years of VAX CPU time.
Others have suggested approaches for solving assignment problems utilizing neural networks. Such systems are called neural networks because of their similarity to biological networks in their structure and in their ability to exhibit self-learning. For example, see U.S. Pat. No. 4,660,166, issued to J. Hopfield, where a type of neural network is used to solve the Traveling Salesman Problem. Others have suggested the use of a neural network technique known as simulated annealing. See S. Kirkpatrick, Gelatt, and Vecchi: "Optimization by Simulated Annealing", 220 Science, p. 671-680 (1983). However, while algorithms using this approach have been developed, to the applicant's knowledge, actual working architectures have not been implemented. Also, neural nets such as the one described in U.S. Pat. No. 4,660,166 are generally not fast enough for real-time applications of reasonable complexity. Recent results suggest severe limitations to the size of problems addressable by Hopfield nets. For example, the traveling salesman problem fails for more than thirty cities.
Thus it would be desirable to provide an information processor that reduces the computation time required to solve constrained assignment problems of realistic sizes in real-time.